package org.example.node;

import com.google.common.collect.Lists;
import lombok.Data;
import lombok.EqualsAndHashCode;
import org.apache.commons.collections.CollectionUtils;
import org.example.BalancePlusTree;
import org.example.bo.SearchResultBO;
import org.example.bo.SimpleEntry;

import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

import static org.example.enums.SearchResultEnum.FOUND;
import static org.example.enums.SearchResultEnum.NOT_FOUND;

/**
 * 索引节点
 *
 * @author lik
 */
@EqualsAndHashCode(callSuper = false)
@Data
public class IndexNode<K extends Comparable<K>, V> extends AbstractNode<K, V> {

    /**
     * 索引节点的子节点
     */
    private List<Map.Entry<K, AbstractNode<K, V>>> children;

    /**
     * 父节点
     */
    private IndexNode<K, V> parent;

    public void addChildren(Map.Entry<K, AbstractNode<K, V>> old, Map.Entry<K, AbstractNode<K, V>> first, Map.Entry<K, AbstractNode<K, V>> second, BalancePlusTree<K, V> balancePlusTree) {
        if (CollectionUtils.isEmpty(children)) {
            children = Lists.newArrayListWithCapacity(DEGREE);
            children.add(first);
            children.add(second);
        } else {
            List<K> keyList = children.stream().map(Map.Entry::getKey).collect(Collectors.toList());
            SearchResultBO removeSearchResult = commonBinarySearch(keyList, old.getKey());
            K currentNodeKey = null;
            if (removeSearchResult.getResult() == FOUND) {
                // 找到旧值则移除
                children.remove((int) removeSearchResult.getPosition());
                // 如果删除的是父节点关联的key 需要更新父节点key索引
                if (removeSearchResult.getPosition() == 0) {
                    currentNodeKey = old.getKey();
                }
            }

            // 添加新的子节点
            for (Map.Entry<K, AbstractNode<K, V>> entry : Lists.newArrayList(first, second)) {
                keyList = children.stream().map(Map.Entry::getKey).collect(Collectors.toList());
                SearchResultBO searchResult = commonBinarySearch(keyList, entry.getKey());
                if (searchResult.getResult() == FOUND) {
                    throw new IllegalStateException("DuplicateKeyException 新对象的key重复了喂");
                }
                children.add(searchResult.getPosition(), entry);
            }

            // 更新父节点索引
            if (currentNodeKey != null && parent != null) {
                parent.updateIndex(currentNodeKey, getMinimumKey());
            }
        }

        // 超过定义的度了
        if (children.size() > DEGREE) {
            // 分裂 平衡
            division(balancePlusTree);
        }
    }

    private void division(BalancePlusTree<K, V> balancePlusTree) {
        int middle = children.size() / 2 + 1;

        // 分裂一个左节点
        IndexNode<K, V> left = new IndexNode<>();
        left.setChildren(Lists.newArrayList(children.subList(0, middle)));
        left.resetParent();

        // 分裂一个右节点
        IndexNode<K, V> right = new IndexNode<>();
        right.setChildren(Lists.newArrayList(children.subList(middle, children.size())));
        right.resetParent();

        SimpleEntry<K, AbstractNode<K, V>> entry1 = new SimpleEntry<>(left.getMinimumKey(), left);
        SimpleEntry<K, AbstractNode<K, V>> entry2 = new SimpleEntry<>(right.getMinimumKey(), right);

        if (parent == null) {
            // 如果父节点为空，那么当前节点就是根节点，分裂后需要新增父节点
            IndexNode<K, V> parent = new IndexNode<>();
            List<Map.Entry<K, AbstractNode<K, V>>> children = Lists.newArrayListWithCapacity(DEGREE);
            balancePlusTree.setRoot(parent);

            children.add(entry1);
            children.add(entry2);
            parent.setChildren(children);

            left.setParent(parent);
            right.setParent(parent);
        } else {
            left.setParent(parent);
            right.setParent(parent);
            // 父节点添加分裂后的子节点
            SimpleEntry<K, AbstractNode<K, V>> currentNode = new SimpleEntry<>(getMinimumKey(), this);
            parent.addChildren(currentNode, entry1, entry2, balancePlusTree);
        }
    }

    /**
     * 重置父节点
     */
    private void resetParent() {
        if (CollectionUtils.isNotEmpty(children)) {
            for (Map.Entry<K, AbstractNode<K, V>> child : children) {
                child.getValue().setParent(this);
            }
        }
    }

    @Override
    public V query(K key) {
        List<K> keyList = children.stream().map(Map.Entry::getKey).collect(Collectors.toList());
        SearchResultBO searchResult = commonBinarySearch(keyList, key);
        if (searchResult.getResult() == FOUND) {
            return children.get(searchResult.getPosition()).getValue().query(key);
        } else {
            int index = searchResult.getPosition() - 1;
            if (index >= 0) {
                return children.get(index).getValue().query(key);
            }
        }
        return null;
    }

    @Override
    public void delete(K key) {
        List<K> keyList = children.stream().map(Map.Entry::getKey).collect(Collectors.toList());
        SearchResultBO searchResult = commonBinarySearch(keyList, key);
        if (searchResult.getResult() == FOUND) {
            children.get(searchResult.getPosition()).getValue().delete(key);
        } else {
            int index = searchResult.getPosition() - 1;
            if (index >= 0) {
                children.get(index).getValue().delete(key);
            }
        }
    }

    @Override
    public void setParent(AbstractNode<K, V> parent) {
        if (parent instanceof IndexNode) {
            this.parent = (IndexNode<K, V>) parent;
            return;
        }
        throw new IllegalArgumentException("父类类型不匹配哦");
    }

    @Override
    public void insertOrUpdate(K key, V value, BalancePlusTree<K, V> balancePlusTree) {
        List<K> keyList = children.stream().map(Map.Entry::getKey).collect(Collectors.toList());
        SearchResultBO searchResult = commonBinarySearch(keyList, key, true);
        if (searchResult.getResult() == NOT_FOUND) {
            if (searchResult.getPosition() >= children.size()) {
                children.get(searchResult.getPosition() - 1).getValue().insertOrUpdate(key, value, balancePlusTree);
            } else {
                children.get(searchResult.getPosition()).getValue().insertOrUpdate(key, value, balancePlusTree);
            }
        } else {
            throw new IllegalStateException("DuplicateKeyException 新对象的key重复了喂");
        }
    }

    @Override
    public K getMinimumKey() {
        if (CollectionUtils.isNotEmpty(children)) {
            return children.get(0).getKey();
        }
        return null;
    }

    public void updateIndex(K oldKey, K newKey) {
        if (oldKey.equals(newKey)) {
            return;
        }
        List<K> keyList = children.stream().map(Map.Entry::getKey).collect(Collectors.toList());
        SearchResultBO searchResult = commonBinarySearch(keyList, oldKey);
        if (searchResult.getResult() == FOUND) {
            Map.Entry<K, AbstractNode<K, V>> entry = children.get(searchResult.getPosition());
            children.set(searchResult.getPosition(), new SimpleEntry<>(newKey, entry.getValue()));
        } else {
            throw new NullPointerException("找不到需要更新的旧Key~");
        }
        if (searchResult.getPosition() == 0 && parent != null) {
            parent.updateIndex(oldKey, newKey);
        }
    }

    public void removeIndex(K key) {
        List<K> keyList = children.stream().map(Map.Entry::getKey).collect(Collectors.toList());
        SearchResultBO searchResult = commonBinarySearch(keyList, key);
        if (searchResult.getResult() == FOUND) {
            // 当前节点原始的key
            K oldKey = getMinimumKey();
            children.remove((int) searchResult.getPosition());
            // 检查当前节点的平衡
            if (children.size() < MINIMUM_VALUE && parent != null) {
                // 往左右兄弟节点借
                IndexNode<K, V> previousNode = parent.getPreviousNode(oldKey);
                if (previousNode != null) {
                    // 左边兄弟如果借了，previousAfterSize就是调整之后的数据长度。
                    // 也是左边兄弟最后数据的位置
                    int previousAfterSize = previousNode.getChildren().size() - 1;
                    if (previousAfterSize >= MINIMUM_VALUE) {
                        // 左边的兄弟说可以借
                        Map.Entry<K, AbstractNode<K, V>> borrowEntry = previousNode.getChildren().get(previousAfterSize);
                        children.add(0, borrowEntry);
                        previousNode.getChildren().remove(previousAfterSize);
                        // 更新父节点索引
                        parent.updateIndex(oldKey, borrowEntry.getKey());
                    } else {
                        // 左边的兄弟说 我也不够了，那就合并了呗，往左合并
                        previousNode.getChildren().addAll(children);
                        // 父节点移除当前叶子结点
                        parent.removeIndex(oldKey);
                    }
                } else {
                    IndexNode<K, V> nextNode = parent.getNextNode(oldKey);
                    if (nextNode != null && nextNode.getParent() != null) {
                        // 右边的兄弟节点
                        int nextAfterSize = nextNode.getChildren().size() - 1;
                        if (nextAfterSize >= MINIMUM_VALUE) {
                            // 右边的兄弟说可以借
                            Map.Entry<K, AbstractNode<K, V>> borrowEntry = nextNode.getChildren().get(0);
                            children.add(borrowEntry);
                            nextNode.getChildren().remove(0);
                            // 更新节点索引
                            nextNode.getParent().updateIndex(borrowEntry.getKey(), nextNode.getMinimumKey());
                            // 当前节点如果删除的是0号位的索引值，需要更新父节点索引
                            if (searchResult.getPosition() == 0) {
                                parent.updateIndex(oldKey, getMinimumKey());
                            }
                        } else {
                            // 右边的兄弟说 我也不够了，那就合并了呗，往当前节点合并
                            children.addAll(nextNode.getChildren());
                            // 父节点移除右边叶子结点
                            nextNode.getParent().removeIndex(oldKey);
                        }
                    } else if (searchResult.getPosition() == 0 && parent != null) {
                        // 如果删除的是0号位的索引值，需要更新父节点索引
                        parent.updateIndex(oldKey, getMinimumKey());
                    }
                }
            }

        } else {
            throw new NullPointerException("找不到需要更新的旧Key = " + key);
        }
    }

    public IndexNode<K,V> getNextNode(K key) {
        List<K> keyList = children.stream().map(Map.Entry::getKey).collect(Collectors.toList());
        SearchResultBO searchResult = commonBinarySearch(keyList, key);
        if (searchResult.getResult() == FOUND) {
            int nextPosition = searchResult.getPosition() + 1;
            if (nextPosition < children.size()) {
                return getByPosition(nextPosition);
            }
        }
        return null;
    }

    public IndexNode<K, V> getPreviousNode(K key) {
        List<K> keyList = children.stream().map(Map.Entry::getKey).collect(Collectors.toList());
        SearchResultBO searchResult = commonBinarySearch(keyList, key);
        if (searchResult.getResult() == FOUND) {
            int previousPosition = searchResult.getPosition() - 1;
            if (previousPosition >= 0) {
                return getByPosition(previousPosition);
            }
        }
        return null;
    }

    private IndexNode<K, V> getByPosition(int position) {
        Map.Entry<K, AbstractNode<K, V>> entry = children.get(position);
        if (entry != null && entry.getValue() != null && entry.getValue() instanceof IndexNode) {
            return (IndexNode<K, V>) entry.getValue();
        }
        return null;
    }
}
